import java.util.*;

/**
 * @program: LeetCode017
 * @author: JCM
 * @create: 2022-11-17 20:59
 * @description: 电话号码的字母组合
 **/
public class test {
    public static void main(String[] args) {
        String s = "23";
        //List<String> list = letterCombinations1(s);
        List<String> list = letterCombinations(s);
        System.out.println(list.toString());
    }

    private static List<String> letterCombinations1(String s) {
        List<String> combinations = new ArrayList<String>();
        if(s.length() == 0) {
            return combinations;
        }
        Map<Character,String> phoneMap = new HashMap<Character,String>() {{
            put('2',"abc");
            put('3',"def");
            put('4',"ghi");
            put('5',"jkl");
            put('6',"mno");
            put('7',"pqrs");
            put('8',"tuv");
            put('9',"wxyz");
        }};
        backtrack1(combinations,phoneMap,s,0,new StringBuffer());
        return combinations;
    }

    private static void backtrack1(List<String> combinations, Map<Character, String> phoneMap, String s, int index, StringBuffer combination) {
        if (index == s.length()) {
            combinations.add(combination.toString());
        }else {
            char digit = s.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack1(combinations,phoneMap,s,index+1,combination);
                combination.deleteCharAt(index);
            }
        }
    }

    private static List<String> letterCombinations(String s) {
        List<String> combinations = new ArrayList<>();
        if(s.length() == 0) {
            return combinations;
        }
        String[] map = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        backtrack(combinations,map,s,0,new StringBuffer());
        return combinations;

    }

    private static void backtrack(List<String> combinations, String[] map, String s, int index, StringBuffer combination) {
        if(index >= s.length()) {
            combinations.add(combination.toString());
        }else {
            int num = s.charAt(index)-'2';
            for(int i = 0 ; i<map[num].length(); i++) {
                combination.append(map[num].charAt(i));
                backtrack(combinations,map,s,index+1,combination);
                combination.deleteCharAt(index);
            }
        }
    }
}
